require(GGally, quietly = TRUE)
require(reshape2, quietly = TRUE)
require(tidyverse, quietly = TRUE, warn.conflicts = FALSE)
package ‘tidyverse’ was built under R version 3.3.2package ‘ggplot2’ was built under R version 3.3.2package ‘tibble’ was built under R version 3.3.2package ‘tidyr’ was built under R version 3.3.2
library(ggfortify)
library(cluster)
library(ggdendro)
library(broom)
theme_set(theme_bw())
source("github-lib.R")
dw %>% 
    select(-repository_language) %>% 
    ggpairs()

 plot: [1,1] [===---------------------------------------]  6% est: 0s 
 plot: [1,2] [=====-------------------------------------] 12% est: 1s 
 plot: [1,3] [========----------------------------------] 19% est: 1s 
 plot: [1,4] [==========--------------------------------] 25% est: 1s 
 plot: [2,1] [=============-----------------------------] 31% est: 1s 
 plot: [2,2] [================--------------------------] 38% est: 1s 
 plot: [2,3] [==================------------------------] 44% est: 1s 
 plot: [2,4] [=====================---------------------] 50% est: 1s 
 plot: [3,1] [========================------------------] 56% est: 1s 
 plot: [3,2] [==========================----------------] 62% est: 1s 
 plot: [3,3] [=============================-------------] 69% est: 0s 
 plot: [3,4] [================================----------] 75% est: 0s 
 plot: [4,1] [==================================--------] 81% est: 0s 
 plot: [4,2] [=====================================-----] 88% est: 0s 
 plot: [4,3] [=======================================---] 94% est: 0s 
 plot: [4,4] [==========================================]100% est: 0s 
                                                                      

As variáveis são bastante assimétricas e concentradas em pequenos valores. Transformá-las para log ajuda na visualização.

dw2.scaled %>% 
    select(-repository_language) %>% 
    ggpairs()

 plot: [1,1] [===---------------------------------------]  6% est: 0s 
 plot: [1,2] [=====-------------------------------------] 12% est: 1s 
 plot: [1,3] [========----------------------------------] 19% est: 1s 
 plot: [1,4] [==========--------------------------------] 25% est: 1s 
 plot: [2,1] [=============-----------------------------] 31% est: 1s 
 plot: [2,2] [================--------------------------] 38% est: 1s 
 plot: [2,3] [==================------------------------] 44% est: 1s 
 plot: [2,4] [=====================---------------------] 50% est: 1s 
 plot: [3,1] [========================------------------] 56% est: 1s 
 plot: [3,2] [==========================----------------] 62% est: 1s 
 plot: [3,3] [=============================-------------] 69% est: 0s 
 plot: [3,4] [================================----------] 75% est: 0s 
 plot: [4,1] [==================================--------] 81% est: 0s 
 plot: [4,2] [=====================================-----] 88% est: 0s 
 plot: [4,3] [=======================================---] 94% est: 0s 
 plot: [4,4] [==========================================]100% est: 0s 
                                                                      

hc %>% 
               cutree(k = n_clusters)
  ActionScript            Ada           Agda          ANTLR           Apex    AppleScript            Arc        Arduino            ASP 
             1              2              1              2              3              1              1              1              1 
      Assembly         Augeas     AutoHotkey         AutoIt            Awk     BlitzBasic   Brightscript              C             C# 
             4              3              1              1              1              4              4              4              4 
           C++         Ceylon        Clojure          COBOL   CoffeeScript     ColdFusion    Common Lisp            Coq        Crystal 
             4              2              4              4              4              1              1              2              4 
           CSS              D           Dart    DCPU-16 ASM         Delphi            DOT          Dylan            Ecl         Eiffel 
             4              1              4              2              2              1              2              2              3 
        Elixir            Elm     Emacs Lisp         Erlang             F#         Factor          Fancy        FORTRAN             Go 
             4              1              1              1              4              3              2              1              4 
          Gosu         Groovy        Haskell           Haxe           HaXe            IDL          Idris           Java     JavaScript 
             1              1              1              4              2              4              1              4              4 
         Julia         Kotlin     LiveScript          Logos            Lua              M         Matlab            Max          Mirah 
             4              1              4              1              1              1              1              3              2 
        Monkey     MoonScript        Nemerle           nesC        NetLogo         Nimrod    Objective-C    Objective-J          OCaml 
             2              2              1              4              2              3              4              3              1 
           ooc            Opa   OpenEdge ABL        Oxygene         Parrot         Pascal           Perl          Perl6            PHP 
             2              2              1              1              3              1              1              2              4 
    PogoScript     PowerShell     Processing         Prolog         Puppet      Pure Data         Python              R         Racket 
             2              1              1              1              1              2              4              1              1 
     REALbasic          Rebol RobotFramework           Ruby           Rust          Scala         Scheme         Scilab           Self 
             2              2              3              1              4              4              1              2              1 
         Shell          Slash      Smalltalk       Squirrel    Standard ML  SuperCollider            Tcl            TeX         Turing 
             1              4              2              2              4              2              1              4              2 
    TypeScript   UnrealScript           Vala        Verilog           VHDL           VimL   Visual Basic           wisp             XC 
             4              2              4              1              2              1              1              3              2 
         XProc         XQuery           XSLT          Xtend 
             2              1              4              1 
library(plotly)
package ‘plotly’ was built under R version 3.3.2
Attaching package: ‘plotly’

The following object is masked from ‘package:ggplot2’:

    last_plot

The following object is masked from ‘package:stats’:

    filter

The following object is masked from ‘package:graphics’:

    layout
p <- dw2 %>%
    plot_ly(type = 'parcoords',
            line = list(color = ~cluster),
            dimensions = list(
                #list(range = c(1, 4), label = "cluster", values = ~cluster),
                list(range = c(0, 4),
                     label = 'Forks/repo', values = ~ForkEvent),
                list(range = c(0, 4),
                     constraintrange = c(5,6),
                     label = 'Issues/repo', values = ~IssuesEvent),
                list(range = c(0, 4),
                     label = 'Pushes/repo', values = ~PushEvent),
                list(range = c(0, 4),
                     label = 'Watches/repo', values = ~WatchEvent)
            )
    )
p

k-means

# O agrupamento de fato:
km = dw2.scaled %>% 
    select(-repository_language) %>% 
    kmeans(centers = n_clusters, nstart = 20)
# O df em formato longo, para visualização 
dw2.scaled.km.long = km %>% 
    augment(dw2.scaled) %>% # Adiciona o resultado de km 
                            # aos dados originais dw2.scaled em 
                            # uma variável chamada .cluster
    gather(key = "variável", 
           value = "valor", 
           -repository_language, -.cluster) # = move para long todas as 
                                            # variávies menos repository_language 
                                            # e .cluster
dw2.scaled.km.long %>% 
    ggplot(aes(x = `variável`, y = valor, group = repository_language, colour = .cluster)) + 
    #geom_point(alpha = 0.2) + 
    geom_line(alpha = .5) + 
    facet_wrap(~ .cluster) 
autoplot(km, data = dw2.scaled, label = TRUE)

dists = dw2.scaled %>% 
    select(-repository_language) %>% 
    dist() # só para plotar silhouetas depois
plot(silhouette(km$cluster, dists), col = RColorBrewer::brewer.pal(n_clusters, "Set2"))

Qual seria um bom valor de k? Uma medida comumente usada no kmeans é comparar a distância (quadrática) entre o centro dos clusters e o centro dos dados com a distância (quadrática) entre os pontos todos nos dados e o centro dos dados. Aqui o centro dos dados é um ponto imaginário na média de todas as variáveis. Calculamos a distância do centro de cada cluster para o centro dos dados e multiplicamos pelo número de pontos nesse cluster. Somando esse valor para todos os clusters, temos betweenss abaixo. Se esse valor for próximo do somatório total das distâncias dos pontos para o centro dos dados (totss), os pontos estão próximos do centro de seu cluster. Essa proporção pode ser usada para definir um bom valor de k. Quando ela para de crescer, para de valer à pena aumentar k.

set.seed(123)
explorando_k = tibble(k = 1:15) %>% 
    group_by(k) %>% 
    do(
        kmeans(select(dw2.scaled, -repository_language), 
               centers = .$k, 
               nstart = 20) %>% glance()
    )
explorando_k %>% 
    ggplot(aes(x = k, y = betweenss / totss)) + 
    geom_line() + 
    geom_point()


K-means

Mais um exemplo

O dataset ruspini é clássico para ilustrar agrupamento.

Hierárquico

dists = dist(rs, method = "euclidean")
hc = hclust(dists, method = "ward.D")

plot(hc, hang = -1, cex = 0.8)

rect.hclust(hc, k=4)

rs$cluster = factor(cutree(hc, k=4))

ggplot(rs, aes(x = x, y = y, colour = cluster)) + 
  geom_point(size = 3) 

rs$cluster = factor(cutree(hc, k=8))
ggplot(rs, aes(x = x, y = y, colour = cluster, label = cluster)) + 
  geom_point(size = 2) + 
  geom_text(hjust = -.1, vjust = 1) + 
  xlim(0, 150)

plot(silhouette(cutree(hc, k = 4), dists))
plot(silhouette(cutree(hc, k = 6), dists))

#heatmap(as.matrix(dw2[,1:4]), Colv=F, scale='none')
#hc.data <- dendro_data(hc)
#ggdendrogram(hc.data, rotate = TRUE) + 
  #labs(title = "Agrupamento de Rustini")
km <- kmeans(rs, centers=4, nstart=10)
km

autoplot(km, data = rs)

autoplot(km, data = rs, frame = TRUE)
LS0tCnRpdGxlOiAiS21lYW5zIGUgbWFpcyBleGVtcGxvcyIKYXV0aG9yOiAiTmF6YXJlbm8gQW5kcmFkZSIKZGF0ZTogIjMwIGRlIG1hcsOnbyBkZSAyMDE2IgpvdXRwdXQ6IAogICAgaHRtbF9ub3RlYm9vawplZGl0b3Jfb3B0aW9uczogCiAgY2h1bmtfb3V0cHV0X3R5cGU6IGlubGluZQotLS0KCmBgYHtyLCBtZXNzYWdlPUZBTFNFfQpyZXF1aXJlKEdHYWxseSwgcXVpZXRseSA9IFRSVUUpCnJlcXVpcmUocmVzaGFwZTIsIHF1aWV0bHkgPSBUUlVFKQpyZXF1aXJlKHRpZHl2ZXJzZSwgcXVpZXRseSA9IFRSVUUsIHdhcm4uY29uZmxpY3RzID0gRkFMU0UpCmxpYnJhcnkoZ2dmb3J0aWZ5KQpsaWJyYXJ5KGNsdXN0ZXIpCmxpYnJhcnkoZ2dkZW5kcm8pCmxpYnJhcnkoYnJvb20pCgp0aGVtZV9zZXQodGhlbWVfYncoKSkKc291cmNlKCJnaXRodWItbGliLlIiKQpgYGAKCmBgYHtyfQpkdyA8LSBsb2FkX2dpdGh1Yl93aWRlKCkKc3VtbWFyeShkdykKCmR3ICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgojIFhNTCBlIEJsdWVzcGVjIHTDqm0gbWFpcyBkZSA1MCBwdXNoZXMgLyByZXBvc2l0w7NyaW8gZSAKIyBvdXRyYXMgbGluZ3VhZ2VucyB0w6ptIHRhbWLDqW0gbsO6bWVyb3MgZXN0cmFuaG9zLiBGaWx0cmFyZW1vcy4KZHcgPC0gZHcgJT4lIAogIGZpbHRlcihQdXNoRXZlbnQgPCA1MCwgSXNzdWVzRXZlbnQgPCA1MCwgRm9ya0V2ZW50IDwgMTgpCmBgYAoKQXMgdmFyacOhdmVpcyBzw6NvIGJhc3RhbnRlIGFzc2ltw6l0cmljYXMgZSBjb25jZW50cmFkYXMgZW0gcGVxdWVub3MgdmFsb3Jlcy4gVHJhbnNmb3Jtw6EtbGFzIHBhcmEgbG9nIGFqdWRhIG5hIHZpc3VhbGl6YcOnw6NvLgoKYGBge3J9CiMgRXNjYWxhIGRlIGxvZyAKZHcyIDwtIGR3ICU+JSAKICAgIG11dGF0ZV9lYWNoKGZ1bnMobG9nKSwgMjo1KQoKZHcyICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgpzdW1tYXJ5KHNlbGVjdChkdzIsIC1yZXBvc2l0b3J5X2xhbmd1YWdlKSkKCmR3Mi5zY2FsZWQgPSBkdzIgJT4lIAogIG11dGF0ZV9lYWNoKGZ1bnMoYXMudmVjdG9yKHNjYWxlKC4pKSksIDI6NSkKc3VtbWFyeShkdzIuc2NhbGVkKQoKZHcyLnNjYWxlZCAlPiUgCiAgICBzZWxlY3QoLXJlcG9zaXRvcnlfbGFuZ3VhZ2UpICU+JSAKICAgIGdncGFpcnMoKQoKYGBgCgoKYGBge3J9CmRpc3RzID0gZHcyLnNjYWxlZCAlPiUgCiAgICBjb2x1bW5fdG9fcm93bmFtZXMoInJlcG9zaXRvcnlfbGFuZ3VhZ2UiKSAlPiUgCiAgICBkaXN0KG1ldGhvZCA9ICJldWNsaWRlYW4iKQpoYyA9IGhjbHVzdChkaXN0cywgbWV0aG9kID0gIndhcmQuRCIpCgpwbG90KGhjLCBjZXggPSAuNikKcGxvdChoYywgaGFuZyA9IC0xKQoKbl9jbHVzdGVycyA9IDQKcmVjdC5oY2x1c3QoaGMsIGs9bl9jbHVzdGVycykKCmR3MiA8LSBkdzIgJT4lIAogICAgbXV0YXRlKGNsdXN0ZXIgPSBoYyAlPiUgCiAgICAgICAgICAgICAgIGN1dHJlZShrID0gbl9jbHVzdGVycykgJT4lIAogICAgICAgICAgICAgICBhcy5jaGFyYWN0ZXIoKSkKCmR3Mi5zY2FsZWQgPC0gZHcyLnNjYWxlZCAlPiUgCiAgICBtdXRhdGUoY2x1c3RlciA9IGhjICU+JSAKICAgICAgICAgICAgICAgY3V0cmVlKGsgPSBuX2NsdXN0ZXJzKSAlPiUgCiAgICAgICAgICAgICAgIGFzLmNoYXJhY3RlcigpKQoKZHcyLmxvbmcgPSBtZWx0KGR3Mi5zY2FsZWQsIGlkLnZhcnMgPSBjKCJyZXBvc2l0b3J5X2xhbmd1YWdlIiwgImNsdXN0ZXIiKSkKCmhjICU+JSAKICAgIGN1dHJlZShrID0gbl9jbHVzdGVycykgJT4lIAogICAgc2lsaG91ZXR0ZShkaXN0cykgJT4lIAogICAgcGxvdChjb2wgPSBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwobl9jbHVzdGVycywgIlNldDIiKSkKCmR3Mi5sb25nICU+JSAKICAgIGdncGxvdChhZXMoeCA9IHZhcmlhYmxlLCB5ID0gdmFsdWUsIGdyb3VwID0gcmVwb3NpdG9yeV9sYW5ndWFnZSwgY29sb3VyID0gY2x1c3RlcikpICsgCiAgICBnZW9tX2xpbmUoYWxwaGEgPSAwLjQpICsgCiAgICBmYWNldF93cmFwKH4gY2x1c3RlcikgCgpgYGAKCmBgYHtyfQpsaWJyYXJ5KHBsb3RseSkKcCA8LSBkdzIgJT4lCiAgICBwbG90X2x5KHR5cGUgPSAncGFyY29vcmRzJywKICAgICAgICAgICAgbGluZSA9IGxpc3QoY29sb3IgPSB+Y2x1c3RlciksCiAgICAgICAgICAgIGRpbWVuc2lvbnMgPSBsaXN0KAogICAgICAgICAgICAgICAgI2xpc3QocmFuZ2UgPSBjKDEsIDQpLCBsYWJlbCA9ICJjbHVzdGVyIiwgdmFsdWVzID0gfmNsdXN0ZXIpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ0ZvcmtzL3JlcG8nLCB2YWx1ZXMgPSB+Rm9ya0V2ZW50KSwKICAgICAgICAgICAgICAgIGxpc3QocmFuZ2UgPSBjKDAsIDQpLAogICAgICAgICAgICAgICAgICAgICBjb25zdHJhaW50cmFuZ2UgPSBjKDUsNiksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ0lzc3Vlcy9yZXBvJywgdmFsdWVzID0gfklzc3Vlc0V2ZW50KSwKICAgICAgICAgICAgICAgIGxpc3QocmFuZ2UgPSBjKDAsIDQpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdQdXNoZXMvcmVwbycsIHZhbHVlcyA9IH5QdXNoRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ1dhdGNoZXMvcmVwbycsIHZhbHVlcyA9IH5XYXRjaEV2ZW50KQogICAgICAgICAgICApCiAgICApCnAKYGBgCgoKIyMgay1tZWFucwoKYGBge3J9CmR3Mi5zY2FsZWQgPSBkdzIuc2NhbGVkICU+JSAKICAgIHNlbGVjdCgtY2x1c3RlcikgIyBSZW1vdmUgbyBjbHVzdGVyIGFkaWNpb25hZG8gYW50ZXMgbMOhIGVtIGNpbWEgdmlhIGhjbHVzdAoKIyBPIGFncnVwYW1lbnRvIGRlIGZhdG86CmttID0gZHcyLnNjYWxlZCAlPiUgCiAgICBzZWxlY3QoLXJlcG9zaXRvcnlfbGFuZ3VhZ2UpICU+JSAKICAgIGttZWFucyhjZW50ZXJzID0gbl9jbHVzdGVycywgbnN0YXJ0ID0gMjApCgojIE8gZGYgZW0gZm9ybWF0byBsb25nbywgcGFyYSB2aXN1YWxpemHDp8OjbyAKZHcyLnNjYWxlZC5rbS5sb25nID0ga20gJT4lIAogICAgYXVnbWVudChkdzIuc2NhbGVkKSAlPiUgIyBBZGljaW9uYSBvIHJlc3VsdGFkbyBkZSBrbSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgYW9zIGRhZG9zIG9yaWdpbmFpcyBkdzIuc2NhbGVkIGVtIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB1bWEgdmFyacOhdmVsIGNoYW1hZGEgLmNsdXN0ZXIKICAgIGdhdGhlcihrZXkgPSAidmFyacOhdmVsIiwgCiAgICAgICAgICAgdmFsdWUgPSAidmFsb3IiLCAKICAgICAgICAgICAtcmVwb3NpdG9yeV9sYW5ndWFnZSwgLS5jbHVzdGVyKSAjID0gbW92ZSBwYXJhIGxvbmcgdG9kYXMgYXMgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB2YXJpw6F2aWVzIG1lbm9zIHJlcG9zaXRvcnlfbGFuZ3VhZ2UgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBlIC5jbHVzdGVyCgpkdzIuc2NhbGVkLmttLmxvbmcgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gYHZhcmnDoXZlbGAsIHkgPSB2YWxvciwgZ3JvdXAgPSByZXBvc2l0b3J5X2xhbmd1YWdlLCBjb2xvdXIgPSAuY2x1c3RlcikpICsgCiAgICAjZ2VvbV9wb2ludChhbHBoYSA9IDAuMikgKyAKICAgIGdlb21fbGluZShhbHBoYSA9IC41KSArIAogICAgZmFjZXRfd3JhcCh+IC5jbHVzdGVyKSAKCmF1dG9wbG90KGttLCBkYXRhID0gZHcyLnNjYWxlZCwgbGFiZWwgPSBUUlVFKQoKZGlzdHMgPSBkdzIuc2NhbGVkICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZGlzdCgpICMgc8OzIHBhcmEgcGxvdGFyIHNpbGhvdWV0YXMgZGVwb2lzCnBsb3Qoc2lsaG91ZXR0ZShrbSRjbHVzdGVyLCBkaXN0cyksIGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbChuX2NsdXN0ZXJzLCAiU2V0MiIpKQoKdGFibGUoa20gJT4lIHB1bGwoY2x1c3RlcikpCmBgYAoKYGBge3J9CiNzdW1tYXJ5KGR3Mi5zY2FsZWQpCnAgPC0ga20gJT4lIAogICAgYXVnbWVudChkdzIuc2NhbGVkKSAlPiUKICAgIHBsb3RfbHkodHlwZSA9ICdwYXJjb29yZHMnLAogICAgICAgICAgICBsaW5lID0gbGlzdChjb2xvciA9IH4uY2x1c3RlciwgCiAgICAgICAgICAgICAgICAgICAgICAgIHNob3dTY2FsZSA9IFRSVUUpLAogICAgICAgICAgICBkaW1lbnNpb25zID0gbGlzdCgKICAgICAgICAgICAgICAgICNsaXN0KHJhbmdlID0gYygxLCA0KSwgbGFiZWwgPSAiY2x1c3RlciIsIHZhbHVlcyA9IH5jbHVzdGVyKSwKICAgICAgICAgICAgICAgIGxpc3QocmFuZ2UgPSBjKC0zLCAzKSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnRm9ya3MvcmVwbycsIHZhbHVlcyA9IH5Gb3JrRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoLTMsIDMpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdJc3N1ZXMvcmVwbycsIHZhbHVlcyA9IH5Jc3N1ZXNFdmVudCksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygtNiwgMyksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ1B1c2hlcy9yZXBvJywgdmFsdWVzID0gflB1c2hFdmVudCksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygtMiwgMyksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ1dhdGNoZXMvcmVwbycsIHZhbHVlcyA9IH5XYXRjaEV2ZW50KQogICAgICAgICAgICApCiAgICApCnAKCmBgYAoKUXVhbCBzZXJpYSB1bSBib20gdmFsb3IgZGUgaz8gVW1hIG1lZGlkYSBjb211bWVudGUgdXNhZGEgbm8ga21lYW5zIMOpIGNvbXBhcmFyIGEgZGlzdMOibmNpYSAocXVhZHLDoXRpY2EpIGVudHJlIG8gY2VudHJvIGRvcyBjbHVzdGVycyBlIG8gY2VudHJvIGRvcyBkYWRvcyBjb20gYSBkaXN0w6JuY2lhIChxdWFkcsOhdGljYSkgZW50cmUgb3MgcG9udG9zIHRvZG9zIG5vcyBkYWRvcyBlIG8gY2VudHJvIGRvcyBkYWRvcy4gQXF1aSBvIGNlbnRybyBkb3MgZGFkb3Mgw6kgdW0gcG9udG8gaW1hZ2luw6FyaW8gbmEgbcOpZGlhIGRlIHRvZGFzIGFzIHZhcmnDoXZlaXMuIENhbGN1bGFtb3MgYSBkaXN0w6JuY2lhIGRvIGNlbnRybyBkZSBjYWRhIGNsdXN0ZXIgcGFyYSBvIGNlbnRybyBkb3MgZGFkb3MgZSBtdWx0aXBsaWNhbW9zIHBlbG8gbsO6bWVybyBkZSBwb250b3MgbmVzc2UgY2x1c3Rlci4gU29tYW5kbyBlc3NlIHZhbG9yIHBhcmEgdG9kb3Mgb3MgY2x1c3RlcnMsIHRlbW9zIGBiZXR3ZWVuc3NgIGFiYWl4by4gU2UgZXNzZSB2YWxvciBmb3IgcHLDs3hpbW8gZG8gc29tYXTDs3JpbyB0b3RhbCBkYXMgZGlzdMOibmNpYXMgZG9zIHBvbnRvcyBwYXJhIG8gY2VudHJvIGRvcyBkYWRvcyAoYHRvdHNzYCksIG9zIHBvbnRvcyBlc3TDo28gcHLDs3hpbW9zIGRvIGNlbnRybyBkZSBzZXUgY2x1c3Rlci4gCkVzc2EgcHJvcG9yw6fDo28gcG9kZSBzZXIgdXNhZGEgcGFyYSBkZWZpbmlyIHVtIGJvbSB2YWxvciBkZSBga2AuIFF1YW5kbyBlbGEgcGFyYSBkZSBjcmVzY2VyLCBwYXJhIGRlIHZhbGVyIMOgIHBlbmEgYXVtZW50YXIgYGtgLgoKYGBge3J9CnNldC5zZWVkKDEyMykKZXhwbG9yYW5kb19rID0gdGliYmxlKGsgPSAxOjE1KSAlPiUgCiAgICBncm91cF9ieShrKSAlPiUgCiAgICBkbygKICAgICAgICBrbWVhbnMoc2VsZWN0KGR3Mi5zY2FsZWQsIC1yZXBvc2l0b3J5X2xhbmd1YWdlKSwgCiAgICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgICBuc3RhcnQgPSAyMCkgJT4lIGdsYW5jZSgpCiAgICApCgpleHBsb3JhbmRvX2sgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IGJldHdlZW5zcyAvIHRvdHNzKSkgKyAKICAgIGdlb21fbGluZSgpICsgCiAgICBnZW9tX3BvaW50KCkKYGBgCgoKLS0tLS0tLS0tLS0tLS0tLS0tLS0KCgojIyBLLW1lYW5zCgpgYGB7cn0KZmlsbWVzID0gcmVhZHI6OnJlYWRfY3N2KCJkYWRvcy9maWxtZXMtc2NhcmxldHQtam9oYW5zc3Nvbi5jc3YiKQoKZmlsbWVzX3QgPSBmaWxtZXMgJT4lIAogICAgc2VsZWN0KC1DUkVESVQpICU+JSAKICAgIG11dGF0ZShgQk9YIE9GRklDRWAgPSBsb2cxMChgQk9YIE9GRklDRWApKSAlPiUgCiAgICBtdXRhdGVfZWFjaChmdW5zKGFzLnZlY3RvcihzY2FsZSguKSkpLCBgQk9YIE9GRklDRWAsIFJBVElORykKCmF0cmlidWljb2VzID0gdGliYmxlKGsgPSAxOjYpICU+JSAKICAgIGdyb3VwX2J5KGspICU+JSAKICAgIGRvKGttZWFucyhzZWxlY3QoZmlsbWVzX3QsIFJBVElORywgYEJPWCBPRkZJQ0VgKSwgCiAgICAgICAgICAgICAgY2VudGVycyA9IC4kaywgCiAgICAgICAgICAgICAgbnN0YXJ0ID0gMTApICU+JSBhdWdtZW50KGZpbG1lcykpICMgYWx0ZXJuZSBlbnRyZSBmaWxtZXMgZSBmaWxtZXNfdCBubyBhdWdtZW50ICAKCmF0cmlidWljb2VzX2xvbmcgPSBhdHJpYnVpY29lcyAlPiUgCiAgICBnYXRoZXIoa2V5ID0gInZhcmlhdmVsIiwgdmFsdWUgPSAidmFsb3IiLCAtVElUTEUsIC1rLCAtLmNsdXN0ZXIsIC1DUkVESVQpIAoKYXRyaWJ1aWNvZXMgJT4lCiAgICBnZ3Bsb3QoYWVzKHggPSBSQVRJTkcsIHkgPSBgQk9YLk9GRklDRWAsIGxhYmVsID0gVElUTEUsIGNvbG91ciA9IC5jbHVzdGVyKSkgKyAKICAgIGdlb21fcG9pbnQoKSArIAogICAgI2dlb21fdGV4dCgpICsgCiAgICBmYWNldF93cmFwKH4gaykgKyBzY2FsZV95X2xvZzEwKCkKCiMgQSBzaWxob3VldGEKZGlzdHMgPSBzZWxlY3QoZmlsbWVzX3QsIFJBVElORywgYEJPWCBPRkZJQ0VgKSAlPiUgZGlzdCgpCmttID0ga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgUkFUSU5HLCBgQk9YIE9GRklDRWApLCAKICAgICAgICAgICAgY2VudGVycyA9IDQsIAogICAgICAgICAgICBuc3RhcnQgPSAxMCkgCgpzaWxob3VldHRlKGttJGNsdXN0ZXIsIGRpc3RzKSAlPiUgCiAgICBwbG90KGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg0LCAiU2V0MiIpKQpgYGAKCmBgYHtyfQpzZXQuc2VlZCgxMjMpCmV4cGxvcmFuZG9fayA9IHRpYmJsZShrID0gMToxNSkgJT4lIAogICAgZ3JvdXBfYnkoaykgJT4lIAogICAgZG8oCiAgICAgICAga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgLVRJVExFKSwgCiAgICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgICBuc3RhcnQgPSAyMCkgJT4lIGdsYW5jZSgpCiAgICApCgpleHBsb3JhbmRvX2sgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IGJldHdlZW5zcyAvIHRvdHNzKSkgKyAKICAgIGdlb21fbGluZSgpICsgCiAgICBnZW9tX3BvaW50KCkKCmBgYAoKCiMgTWFpcyB1bSBleGVtcGxvCgpPIGRhdGFzZXQgcnVzcGluaSDDqSBjbMOhc3NpY28gcGFyYSBpbHVzdHJhciBhZ3J1cGFtZW50by4KCmBgYHtyfQpzdHIocnVzcGluaSkKCmdncGxvdChydXNwaW5pLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKc3VtbWFyeShydXNwaW5pKQoKcnMgPC0gZGF0YS5mcmFtZSgocnVzcGluaSkpCnJzIDwtIGRhdGEuZnJhbWUoc2NhbGUocnVzcGluaSkpCmNvbE1lYW5zKHJzKQoKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKYGBgCgojIyBIaWVyw6FycXVpY28KCmBgYHtyfQpkaXN0cyA9IGRpc3QocnMsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQpoYyA9IGhjbHVzdChkaXN0cywgbWV0aG9kID0gIndhcmQuRCIpCgpwbG90KGhjLCBoYW5nID0gLTEsIGNleCA9IDAuOCkKCnJlY3QuaGNsdXN0KGhjLCBrPTQpCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz00KSkKCmdncGxvdChycywgYWVzKHggPSB4LCB5ID0geSwgY29sb3VyID0gY2x1c3RlcikpICsgCiAgZ2VvbV9wb2ludChzaXplID0gMykgCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz04KSkKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvdXIgPSBjbHVzdGVyLCBsYWJlbCA9IGNsdXN0ZXIpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIpICsgCiAgZ2VvbV90ZXh0KGhqdXN0ID0gLS4xLCB2anVzdCA9IDEpICsgCiAgeGxpbSgwLCAxNTApCgpwbG90KHNpbGhvdWV0dGUoY3V0cmVlKGhjLCBrID0gNCksIGRpc3RzKSkKcGxvdChzaWxob3VldHRlKGN1dHJlZShoYywgayA9IDYpLCBkaXN0cykpCgojaGVhdG1hcChhcy5tYXRyaXgoZHcyWywxOjRdKSwgQ29sdj1GLCBzY2FsZT0nbm9uZScpCiNoYy5kYXRhIDwtIGRlbmRyb19kYXRhKGhjKQojZ2dkZW5kcm9ncmFtKGhjLmRhdGEsIHJvdGF0ZSA9IFRSVUUpICsgCiAgI2xhYnModGl0bGUgPSAiQWdydXBhbWVudG8gZGUgUnVzdGluaSIpCmBgYAoKYGBge3J9CmttIDwtIGttZWFucyhycywgY2VudGVycz00LCBuc3RhcnQ9MTApCmttCgphdXRvcGxvdChrbSwgZGF0YSA9IHJzKQoKYXV0b3Bsb3Qoa20sIGRhdGEgPSBycywgZnJhbWUgPSBUUlVFKQoKYGBgCgo=